This paper presents a new approach to sampling from binary graphical models. There are two main tricks in this paper. The first is a clever construction to transform an arbitrary distribution over binary vectors x into a uniform distribution over an expanded space. This is done by augmenting x with additional bits, which are subject to parity constraints that ensure that the number of is approximately proportional to the original probability of x. This is a uniform distribution over a set with complex nonlinear constraints, so sampling from this distribution is challenging.

Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows. We propose a randomized algorithm that, with high probability, gives a constant-factor approximation of a general discrete integral defined over an exponentially large set. This algorithm relies on solving only a small number of instances of a discrete combinatorial optimization problem subject to randomly generated parity constraints used as a hash function. As an application, we demonstrate that with a small number of MAP queries we can efficiently approximate the partition function of discrete graphical models, which can in turn be used, for instance, for marginal computation or model selection.